package Algorithm.array;

import java.util.ArrayList;

/**
 * desc     : 二分查找高效判定子序列
 * 二分查找本身不难理解，难在巧妙地运用二分查找技巧。对于一个问题，你可能都很难想到它跟二分查找有关，比如前文 最
 * 长递增子序列 就借助一个纸牌游戏衍生出二分查找解法。
 *
 * 今天再讲一道巧用二分查找的算法问题：如何判定字符串 s 是否是字符串 t 的子序列（可以假定 s 长度比较小，且 t 的长度非常大）。
 * 举两个例子：
 *
 * s = "abc", t = "ahbgdc", return true.
 *
 * s = "axc", t = "ahbgdc", return false.
 *
 * 题目很容易理解，而且看起来很简单，但很难想到这个问题跟二分查找有关吧？
 * dateTime : 2020-06-14 23:31
 *
 * @author wwchen
 */
public class IsSubsequence {

    public static void main(String[] args) {

    }

    public static boolean isSubsequence(String s, String t){
        ArrayList<Integer>[] list = new ArrayList[256];
        int n = t.length();
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            if (list[c]==null) list[c] = new ArrayList<>();
            list[c].add(i);
        }

        int m = s.length();
        int j =0;
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            if(list[c]==null) return false;
            int pos = left_bound(list[c], j);
            if (pos == -1) return false;
            j=list[c].get(pos)+1;
        }
        return true;


    }

    static int left_bound(ArrayList<Integer> arr, int tar){
        int lo=0,hi=arr.size()-1;
        while(lo<=hi){
            int mid = lo+(hi-lo)/2;
            if (arr.get(mid)<tar) {
                lo = mid +1;
            } else {
                hi = mid-1;
            }
        }
        if (lo>hi||arr.get(lo)!=tar) return -1;
        return lo;
    }
}
